package com.gaogzhen.algorithms4.foundation;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

import java.io.File;

/**
 * 测试union-find
 */
public class TestUF {
    public static void main(String[] args) {

        // testQF();
        // testQU();
        // testWeightedUF();
       testPathCompress();
    }

    public static void testPathCompress() {
        In in = fetchData();
        int n = in.readInt();
        testUF(new UF(n), in);
    }

    public static void testWeightedUF() {
        In in = fetchData();
        int n = in.readInt();
        testUF(new WeightedQuickUnionUF(n), in);
    }

    private static In fetchData() {
        String path = System.getProperty("user.dir") + File.separator + "asserts/tinyUF.txt";
        return new In(path);
    }

    private static void testUF(UnionFind uf, In in) {
        while (!in.isEmpty()) {
            int p = in.readInt();
            int q = in.readInt();
            if (uf.find(p) == uf.find(q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " components");
    }

    public static void testQU() {
        String path = System.getProperty("user.dir") + File.separator + "asserts/tinyUF.txt";
        In in = new In(path);
        int n = in.readInt();
        QuickUnionUF uf = new QuickUnionUF(n);
        while (!in.isEmpty()) {
            int p = in.readInt();
            int q = in.readInt();
            if (uf.find(p) == uf.find(q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " components");
    }

    public static void testQF() {

        String path = System.getProperty("user.dir") + File.separator + "asserts/tinyUF.txt";
        In in = new In(path);
        int n = in.readInt();
        QuickFindUF uf = new QuickFindUF(n);
        while (in.hasNextLine()) {
            int p = in.readInt();
            int q = in.readInt();
            if (uf.find(p) == uf.find(q)) continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " 连通分量");
    }
}
